package com.剑指offer.第七章队列;

import java.util.LinkedList;
import java.util.Queue;

public class 二叉树最底层最左边的值 {

    /**
     * 用两个队列分别存放在不同层的节点，一个队列存放当前遍历层的节点，另一个队列存放下一层的节点
     *
     * 当队列queuq1被清空时，当前这一层都已经被遍历完了，接下来可以开始下一层的遍历，如果下一层有节点
     * 则用下一层的第一个节点的值更新变量buttomLeft
     * @param node
     * @return
     */
    public static int resolve(TreeNode node) {
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(node);
        int buttomLeft = node.val;
        while (!queue1.isEmpty()) {
            TreeNode poll = queue1.poll();
            if (poll.left != null) {
                queue2.offer(poll.left);
            }
            if (poll.right != null) {
                queue2.offer(poll.right);
            }

            if (queue1.isEmpty()) {
                queue1 = queue2;
                queue2 = new LinkedList<>();
                if (!queue1.isEmpty()) {
                    buttomLeft = queue1.peek().val;
                }
            }
        }
        return buttomLeft;
    }

}
